﻿#define _CRT_SECURE_NO_WARNINGS 1


#include<vector>
#include<iostream>
using namespace std;

class Solution
{
public:
    void duplicateZeros(vector<int>& arr)
    {
        int dest = -1 , cur = 0, n = arr.size();

        while (cur < n)
        {
            if (arr[cur] == 0)
                ++dest;

            ++dest;

            //判断条件
            if (dest >= n - 1)
                break;
            ++cur;
        }

        if (dest >= n)
        {
            arr[n - 1] = 0;
            dest -= 2;
            cur--;
        }

        while (dest >= 0 && cur >= 0)
        {
            if (arr[cur] == 0)
            {
                arr[dest--] = 0;
                arr[dest--] = 0;
            }
            else
            {
                arr[dest--] = arr[cur];
            }
            --cur;
            //--dest;
        }
    }
};

int main()
{
    vector<int> arr({ 1,0,2,3,0,4,5,0 });
    Solution s1;
    s1.duplicateZeros(arr);
    for (auto& e : arr)
    {
        cout << e << "  ";
    }
    cout << endl;

    return 0;
}